/* =============================================================
 * Your Grandmother's guide to Algorithms
 * =============================================================
 *
 * Copyright (c) 2007, Saverio Miroddi
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions are met:
 * 
 *     * Redistributions of source code must retain the above copyright notice,
 *       this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright 
 *       notice, this list of conditions and the following disclaimer in the 
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the SaverioMiroddiSoftware nor the names of its 
 *       contributors may be used to endorse or promote products derived from 
 *       this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *  
 * ---------------------------
 * LeafNode.java
 * ---------------------------
 *
 */
package btree;

import java.util.*;

import btree.BTree.AdditionReturn;
import btree.BTree.DeletionReturn;
import btree.BTree.DeletionReturn.ChildEvent;

/**
 * Represents the leaf node of a b-tree.<br>
 */
@SuppressWarnings("unchecked")
public class LeafNode extends AbstractNode 
{
	private RecElement[] _elements; 
	
	public LeafNode(
			int order) 
	{
		_elements = new RecElement[order];
	}

	@Override
	public AdditionReturn add(
			RecElement inserting) 
	{
		if (findPosition(inserting.value) >= 0) 
			throw new UnsupportedOperationException("non unique");
		
		if (_currentElems < _elements.length) {
			// we're lucky, the node is not full ;-)
			_currentElems = orderedInsertInArray(_elements, _currentElems, inserting);
			return null;
		}
		else {
			// buffer for all elements
			RecElement[] tempElems = new RecElement[_elements.length + 1];			
			System.arraycopy(_elements, 0, tempElems, 0, _elements.length);
			orderedInsertInArray(tempElems, _elements.length, inserting);
			
			/** index of first element to move to the new right node; if odd,
			 * the middle one goes to the left node */
			int firstRightIdx = (int)(Math.ceil((double)tempElems.length / 2));
			
			// copy right elements to the new node, excluding mid;
			// the parent is set by the caller routine
			LeafNode newRightNode = new LeafNode(_elements.length);
			System.arraycopy(tempElems, firstRightIdx, newRightNode._elements, 0, 
							 tempElems.length - firstRightIdx);
			newRightNode._currentElems = tempElems.length - firstRightIdx;
			newRightNode._rightPtr = _rightPtr;
			
			// copy left elements to this node
			System.arraycopy(tempElems, 0, _elements, 0, firstRightIdx - 0);
			Arrays.fill(_elements, firstRightIdx, _currentElems, null);
			_currentElems = firstRightIdx;
			_rightPtr = newRightNode;

			// propagate split up!
			int lastLeftIdx = firstRightIdx - 1;
			NodeElement splitHappens = new NodeElement(_elements[lastLeftIdx].value, this);
			
			return new AdditionReturn(splitHappens, newRightNode); 
		}
	}
	
	@Override
	public long search(Comparable<?> value) 
	{
		int position = findPosition(value);
		if (position >= 0) return _elements[position].recPtr;
		else return BTree.SEARCH_VAL_NOT_FOUND;
	}

	@Override
	public DeletionReturn remove(
		Comparable<?> value, AbstractNode leftSibling, AbstractNode rightSibling)
	{
		int valuePos = findPosition(value);

		if (valuePos < 0) { // exact match not found
			return null;
		}
		else {
			RecElement removed = (RecElement)removeElement(valuePos);

			/* CASE: we are root, no need to propagate anything */
			if (leftSibling == NULL_NODE && rightSibling == NULL_NODE) {
				return new DeletionReturn(ChildEvent.NO_VALUECHG, null);
			}			
			/* CASE: more than min+1 elems */
			else if (hasMinimum()) {
				if (valuePos == _currentElems) {
					Comparable rightmost = _elements[_currentElems - 1].value;
					return new DeletionReturn(ChildEvent.CHANGED_RIGHTMOST, rightmost);
				}
				else {
					return new DeletionReturn(ChildEvent.NO_VALUECHG, removed.value);
				}
			}
			/* CASE: less than min+1 elems; we must borrow from a sibling */
			else {
				return interactWithSibling(leftSibling, rightSibling);
			}
		}
	}

	@Override
	public Iterator<Long> orderedTraversal()
	{
		return new OrderedTraversalIterator(this); 
	}
	
	/**
	 * Slightly different [non-abstractable] from InternalNode one because the latter
	 * need to know the equivalent value of the rightmost pointer.  
	 */
	private DeletionReturn interactWithSibling(
			AbstractNode remLeftPtr, AbstractNode remRightPtr)
	{
		// TODO: steal from the one with more elems
		
		/* First we try to steal to any one has min+1, starting from
		 * right. */ 
		
		if (remRightPtr != null && remRightPtr.hasMinimumPlusOne()) {
			return stealRight(remRightPtr);
		}
	
		if (remLeftPtr != null && remLeftPtr.hasMinimumPlusOne()) {
			return stealLeft(remLeftPtr);
		}
		
		/* Then, if one is not present we merge with the other; otherwise
		 * we merge with the one with less elems */
		
		if (remRightPtr == null) {
			return mergeLeft(remLeftPtr);
		}
		else if (remLeftPtr == null) {
			return mergeRight(remRightPtr);
		}
		else { // if remLeftPtr != null && remRightPtr != null
			// merge with the one with less elems
			if (remLeftPtr._currentElems <= remRightPtr._currentElems) {
				return mergeLeft(remLeftPtr);
			}
			else {
				return mergeRight(remRightPtr);
			}
		}
	}

	private DeletionReturn stealLeft(
			AbstractNode leftPtr)
	{
		LeafNode leftNode = (LeafNode)leftPtr;
		
		AbstractElement stolen = leftNode.removeElement(
				leftNode._currentElems - 1);
		
		System.arraycopy(_elements, 0, _elements, 1, _currentElems);
		_elements[0] = (RecElement)stolen;
		_currentElems++;

		Comparable newLeftNodeRightmostVal = 
			leftNode._elements[leftNode._currentElems - 1].value;
		Comparable thisRightmostVal = _elements[_currentElems - 1].value;
		
		return new DeletionReturn(
				ChildEvent.STOLE_LEFT, thisRightmostVal, newLeftNodeRightmostVal);
	}

	private DeletionReturn stealRight(
			AbstractNode rightPtr)
	{
		AbstractElement stolen = rightPtr.removeElement(0);
		
		// stolen is necessarily greater than every element of this node
		_elements[_currentElems] = (RecElement)stolen;
		_currentElems++;
		
		Comparable newCurrNodeRightmost = stolen.value;
		return new DeletionReturn(ChildEvent.STOLE_RIGHT, newCurrNodeRightmost);
	}
	
	/** @see DeletionReturn.MERGE_LEFT */
	private DeletionReturn mergeLeft(
			AbstractNode node)
	{
		LeafNode left = (LeafNode)node;

		// 1. for leaf nodes, we don't have a leftNode.rightPtr in mezzo ai 
		// maroni
		// 2. the retaining node is the left one

		RecElement[] temp = new RecElement[left._currentElems + _currentElems];
		System.arraycopy(left._elements, 0, temp, 0, left._currentElems);
		System.arraycopy(_elements, 0, temp, left._currentElems, _currentElems);
		left._elements = temp;
		left._currentElems = left._currentElems + _currentElems;
		left._rightPtr = _rightPtr;
		
		Comparable newRightmostValue = left._elements[left._currentElems - 1].value;
		return new DeletionReturn(ChildEvent.MERGE_LEFT, newRightmostValue); 
	}
	
	private DeletionReturn mergeRight(
			AbstractNode node)
	{
		LeafNode right = (LeafNode)node;
		
		RecElement[] temp = new RecElement[right._currentElems + _currentElems];
		System.arraycopy(_elements, 0, temp, 0, _currentElems);
		System.arraycopy(right._elements, 0, temp, _currentElems, right._currentElems);
		_elements = temp;
		_currentElems = right._currentElems + _currentElems;
		_rightPtr = right._rightPtr;
		
		Comparable newRightmostValue = _elements[_currentElems - 1].value;
		return new DeletionReturn(ChildEvent.MERGE_RIGHT, newRightmostValue);
	}

	@Override
	protected Comparable getSubtreeRightmostVal()
	{
		return _elements[_currentElems - 1].value;
	}
	
	@Override
	protected RecElement[] getElementsPtr()
	{
		return _elements;
	}
	
	private static class OrderedTraversalIterator implements Iterator<Long>
	{
		private int _elemPos; 
		private LeafNode _leafPtr;
		
		public OrderedTraversalIterator(
				LeafNode startingLeaf)
		{
			_leafPtr = startingLeaf;			
			// we must start from before than start position!
			_elemPos = -1;
		}
	
		public boolean hasNext()
		{
			// +1 accounts for the next() position
			return (_elemPos + 1 < _leafPtr._currentElems) ||
				   (_leafPtr._rightPtr != null);
		}
		
		public Long next()
		{
			if (! hasNext()) {
				throw new IllegalStateException();
			}
			else {
				_elemPos++;

				if (_elemPos < _leafPtr._currentElems) {
					return _leafPtr._elements[_elemPos].recPtr; 
				}
				else {
					_leafPtr = (LeafNode)_leafPtr._rightPtr;
					_elemPos = 0;
					return _leafPtr._elements[_elemPos].recPtr; 
				}
			}
		}
		
		public void remove()
		{
			throw new UnsupportedOperationException();
		}
	}
	
	////////////////////////////////////////////////////////////////////////////////
	// DEBUG METHODS 
	////////////////////////////////////////////////////////////////////////////////
	
	@Override
	public List<AbstractNode> getChildren()
	{
		return Collections.emptyList();
	}
}